import javax.swing.tree.TreeNode;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/3
 * \* Time: 15:59
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 从中序与后序遍历序列构造二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder,0, inorder.length-1,postorder,0, postorder.length-1 );
    }

    TreeNode build(int[] inorder,int inStart,int inEnd,int[] postorder ,int postStart ,int postEnd){
        if(inStart>inEnd){
            return null;
        }
        //root节点对应后序遍历数组的最后一个元素
        int rootVal=postorder[postEnd];
        int index=0;
        for(int i=inStart;i<=inEnd;i++){
            if(inorder[i]==rootVal){
                index=i;
                break;
            }
        }
        //左子树节点个数
        int leftSize=index-inStart;
        TreeNode root=new TreeNode(rootVal);
        root.left=build(inorder,inStart,index-1,postorder,postStart,postStart+leftSize-1);
        root.right=build(inorder,index+1,inEnd,postorder,postStart+leftSize,postEnd-1);
        return root;
    }
}